#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define MAX_LEN 100

typedef struct expr_t
{
    char op;    /* one of +, *, %, x, N */
    int left;   /* left operand; non-negative constant or ~index */
    int right;  /* right operand; non-negative constant or ~index */
} expr_t;

static expr_t tree[MAX_LEN];    /* expr tree */
static int num_nodes;           /* number of nodes */
static int root;                /* non-negative constant or ~index */
static int M;                   /* modulus */

static void build_expr_tree(const char *s)
{
    int operand_stack[MAX_LEN];
    int num_operands = 0;
    num_nodes = 0;
    for (;;)
    {
        char op;
        while (*s == ' ') /* Skip spaces. */
            s++;

        op = *s++;
        if (op == 'x' || op == 'N') /* variable */
        {
            tree[num_nodes].op = op;
            operand_stack[num_operands++] = ~(num_nodes++);
        }
        else if (op == '+' || op == '*' || op == '%') /* operator */
        {
            tree[num_nodes].op = op;
            tree[num_nodes].right = operand_stack[--num_operands];
            tree[num_nodes].left = operand_stack[--num_operands];
            operand_stack[num_operands++] = ~(num_nodes++);
            if (op == '%')
                break;
        }
        else /* number */
        {
            int num = strtol(s - 1, (char **)&s, 10);
            operand_stack[num_operands++] = num % M;
        }
    }
    root = tree[--num_nodes].left;
}

static int eval(int x, int index)
{
    const expr_t *node;
    if (index >= 0)
        return index;

    node = &tree[~index];
    switch (node->op)
    {
    case '+':
        return (eval(x, node->left) + eval(x, node->right)) % M;
    case '*':
        return (long long)eval(x, node->left) * eval(x, node->right) % M;
    case 'x':
        return x;
    }
    return 0;
}

#define MAX_M   11000000
static int first[MAX_M];    /* first occurrence of a value */

static int solve()
{
    int x;  /* starting value of the sequence */
    int i;
    char line[MAX_LEN+10];

    if (scanf("%d %d", &M, &x) != 2 || M == 0)
        return 0;
    x %= M;

    fgets(line, sizeof(line), stdin);
    build_expr_tree(line);
    memset(first, 0, sizeof(first[0]) * M);

    for (i = 1; ; i++)
    {
#if 0
        printf("f_%d = %d\n", i, x);
#endif
        x = eval(x, root);
        if (first[x] > 0)
        {
            printf("%d\n", i - first[x]);
            break;
        }
        first[x] = i;
    }
    return 1;
}

int main()
{
    while (solve());
    return 0;
}